package com.zhugang.week09;

import java.util.HashSet;

/**
 * @program algorithms
 * @description: findWhetherExistsPath
 * @author: chanzhugang
 * @create: 2022/08/22 23:13
 */
public class FindWhetherExistsPath {

    /**
     * 面试题 04.01 节点间通路
     *
     * @param n
     * @param graph
     * @param start
     * @param end
     * @return
     */
    private boolean[] visited;
    // 邻接表
    private HashSet<Integer>[] adj;
    private boolean found = false;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // leetcode测试用例没通过
        visited = new boolean[n];
        // 构建邻接表
        adj = new HashSet[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new HashSet<>();
        }

        for (int i = 0; i < graph.length; i++) {
            if (!adj[graph[i][0]].contains(graph[i][1])) {
                adj[graph[i][0]].add(graph[i][1]);
            }
        }
        dfs(start, target);
        return found;
    }

    private void dfs(int cur, int target) {
        if (found) return;
        if (cur == target) {
            found = true;
            return;
        }
        visited[cur] = true;
        for (int next : adj[cur]) {
            if (!visited[next]) {
                // 邻接顶点
                dfs(next, target);
            }
        }
    }
}